#include <cstdio>

unsigned int mp[16][16] = {
    {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
    {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

unsigned int dp[32][16];

int main(void)
{
    int re, n;

    for (int j = 0; j < 16; j++)
        dp[0][j] = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= 30; i++) {
        for (int j = 0; j < 16; j++) {
            dp[i][j] = 0;
            for (int k = 0; k < 16; k++) {
                if(mp[k][j] != 0) {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }

    scanf("%d", &re);
    for (int ri = 1; ri <= re; ri++) {
        scanf("%d", &n);
        printf("%d %u\n", ri, dp[n][0]);
    }

    return 0;
}

// Run ID   Submit time     Judge Status    Problem ID  Language    Run time    Run memory      User Name
//2950460   2008-06-15 20:37:31     Accepted    2994    C++     00:00.00    396K    Re:ReJudge

// 2012-09-07 01:53:16 | Accepted | 2994 | C++ | 0 | 184 | watashi | Source
